// ll_task.cpp : Defines the entry point for the console application.
//
// Write a function that would return the 5th element from the end in 
// a singly linked list of integers, in one pass, and then provide a 
// set of test cases against that function

/*
 main.cpp

 Task: Write a function that would return the 5th element from 
 the end in a singly linked list of integers, in one pass

 */

#include "windows.h"
#include "tchar.h"
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <sstream>

using std::string;
using std::cout;
using std::cin;
using std::istringstream;
using std::endl;
using std::setbase;

#define	USED(x)	(void)(x)


typedef struct _ll_data {
	int num;
} ll_data, *P_ll_data;

typedef struct _ll {
	ll_data data;
	struct _ll *pNext;
} ll, *P_ll;

//static ;
int ll_node_count;


void store_ll(P_ll& head, int x)
{
	P_ll node, temp;

	node= (P_ll) new ll;
	node->data.num = x;
	node->pNext = NULL;

	if (!head) {

		head = node;

	}
	else {  // go to the last and append it

		temp = head;

		while (temp->pNext) {

			temp = temp->pNext;

		}

		temp->pNext = node;
	}

	ll_node_count++;
}

void display_ll(P_ll head)
{
	P_ll temp;

	temp = head;

	cout << endl;

	while (temp) {

		cout << " - " << setbase(10) << temp->data.num;

		temp = temp->pNext;

	}
	
	cout << endl;

	return;
}


#define ALL 0
void del_ll (P_ll& head, int node_pos)
{
	P_ll temp, t;

	temp = head;

	while (temp) {

		t= temp->pNext;

		delete temp;

		// temp = t ? t->pNext : NULL;

		temp = t;

	}
	
	head = NULL;

	ll_node_count = 0;

	return;	  
}

/* using 
	Bit 29 - C is set - the Customer code flag   
*/
#define SETBY_APP 0x20000000

//
// get the 'integer' (data) at the node 'idx'
// error reproting  via "error code" 
// 
//  bool get_ll_node(P_ll head, int idx, int& p_node_data)
//
//		returns:
//			true if success and false if function fails
//
//		parameter:
//			P_ll head:	Refers to the head of the linked-list 
//			int idx:	Refers to the Nth element from the end in 
//						a singly linked list - the function has to 
//						find the int stored in this elem  
//			int& p_node_data : valid only if true returned int value stored at 'idx' - 
//   
//		following error set by the function (- Caller to use GetLastError - if 'false' is returned)
//			ERROR_INVALID_PARAMETER - 
//					- if the ll is not initialized (i.e. head is NULL)
//					- if idx < 0					
//			ERROR_INVALID_DATA - 
//					- if idx is more than the number of elems in the list

bool get_ll_node(P_ll head, int idx, int& p_node_data)
{
	if (!head)  {	// check for p_node_data not required becasue we are passing it by reference
		SetLastError(SETBY_APP | ERROR_INVALID_PARAMETER);
		return false;
	}

	if (idx < 0) {
		SetLastError(SETBY_APP | ERROR_INVALID_PARAMETER);
		return false;
	}

	P_ll current, atIdxFromLast;
	
	// move idx elems from begining

	current = head;

	// skip the num idx elems from start
	for (int i = 0; i < idx; i++) {

		if (current->pNext) {

			current = current->pNext;
		}
		else {

			if (i == idx)  // when there are idx number of elems in the ll
				break;

			SetLastError(SETBY_APP | ERROR_INVALID_DATA);

			return false;
		}
	}

	atIdxFromLast = head;

	// walk through rest of the ll, until we get to the end of the ll
	// 
	while (current->pNext) {

		current = current->pNext;

		atIdxFromLast = atIdxFromLast->pNext;
	}

	// atIdxFromLast now points to the elem at 'idx' - 
	// - return the int stored here
	p_node_data =  atIdxFromLast->data.num;

	return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
	USED (argc);
	USED (argv);

	P_ll head = NULL;

	int x;	// integer at the position requested

	int pos = 5;

	/* test cases
		- Case 0: ll has not been created
		- Case 1: total_node_count < pos
		- Case 2: total_node_count == pos
		- Case 3: total_node_count > 1
		- Case 4: total_node_count > pos
		- Case 5: total_node_count > pos
		- Case 6: pos is 0
		- Case 7: pos is -ve
	*/

	// Case 0: ll has not been created
	pos = 5;
	if (get_ll_node(head, pos, x)) {
		cout << " Case 0: get_ll_node has " << x << " at " << pos << endl;
	}
	else {
		cout << " Case 0: get_ll_node fails with " << setbase(16) << GetLastError() << endl;
	}


	// Case 1: list is being loaded as 10, 11, 12
	// Case 2: list is being loaded as 10, 11, 12, 13, 14
	// Case 3: list is being loaded as 10, 11, 12, 13, 14, 15
	// Case 4: list is being loaded as 10, 11, 12, 13, 14, 15, 16
	// Case 5: list is being loaded as 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
	int test_node_count[] = {	3,	// Case 1: create a list with 3 elements
								5,	// Case 2: create a list with 5 elements
								6, 	// Case 3: create a list with 6 elements
								7, 	// Case 4: create a list with 7 elements
								14 	// Case 5: create a list with 14 elements
	};

	int cc, i, total_node_count_limit;

	for (cc=0; cc < 5; cc++) {

		total_node_count_limit = test_node_count[cc];

		for (i=0; i < total_node_count_limit; i++) 
			store_ll(head, 10+i); 

		display_ll(head);

		bool bSuccess = get_ll_node(head, pos, x);

		if (bSuccess) {
			cout << " Case " << cc + 1 << ": get_ll_node has " << x << " at " << pos << "th from last" << endl;
		}
		else {
			cout <<  " Case " << cc + 1 << ": get_ll_node fails with " << setbase(16) << GetLastError() << endl;
		}

		if (cc != 4)	//  do not delete the ll generated for Case 5th ll, it will be reused for other test cases
			del_ll(head, ALL);
	}

	int test_pos[] = {	0,	// Case 6: pos is 0
						-2 // Case 7: pos is -ve
	};

	for (cc = 0; cc < 2; cc++) {

		pos = test_pos[cc];

		bool bSuccess = get_ll_node(head, pos, x);

		if (bSuccess) {
			cout << endl <<  " Case " << cc + 6 << ": get_ll_node has " << x << " at " << pos << "th from last" << endl;
		}
		else {
			cout << endl <<" Case " << cc + 6 << ": get_ll_node fails with " << setbase(16) << GetLastError() << endl;
		}

	}
	
	// since passing by reference  - check for NULL as the third parameter is not required	

	del_ll(head, ALL);

	return 0;
}

